#include <stdio.h>

void Swap(int* p1, int* p2)
{
	int tem = *p1;
	*p1 = *p2;
	*p2 = tem;
}

// 三路划分 -> 处理相等的值
// 1、key 默认取left的值
// 2、prev cur 前后指针处理不相同的值
// 3、遇到和 key 相同的值 直接 ++cur
// 4、遇到小于 key 的值放到前面 和prev交换
// 5、遇到大于key的值放到后面 和end交换
void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
		return;

	int key = a[left];
	int prev = left, cur = left + 1;
	int end = right;

	while (cur <= end)
	{
		if (a[cur] < key)        //  把小的值换到左边
		{
			Swap(&a[prev], &a[cur]);
			++cur;
			++prev;
		}
		else if (a[cur] > a[end])   // 把大的值换到后面
		{
			Swap(&a[cur], &a[end]);
			--end;
		}
		else                       // 值相等的话 就直接 ++cur
			++cur;
	}

	QuickSort1(a, 0, prev - 1);
	QuickSort1(a, cur, right);

}

void AdjustDown(int* a, int parent, int n)
{
	int child = parent * 2 + 1;
	// 向下调整
	while (child < n)
	{
		// 用假设法找出左右子节点最小的那个节点
		if (child + 1 < n && a[child] < a[child + 1])
			child = child + 1;

		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}

// 从下往上 以此向下调整
void HeapSort(int* a, int n)
{
	// 直接走parent的那块 从第一个parent的地方开始
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, i, n);
	}

	for (int i = n - 1; i >= 0; --i)
	{
		//printf("%d ", a[0]);
		Swap(&a[0], &a[i]);
		AdjustDown(a, 0, i);
	}
}

void Print(int* a, int n)
{
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void _QuickSort(int* a, int left, int right, int depth, int rule)
{
	if (left >= right)
		return;

	// 如果深度大于规定的深度就走堆排序
	if (depth >= rule)
	{
		HeapSort(a + left, right - left + 1);
		return;
	}

	int prev = left, cur = left + 1;
	while (cur < right)
	{
		if (a[cur] < a[left])
		{
			if (++prev != cur)
				Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[left], &a[prev]);
	// 每次排完序都给depth加一 增加深度
	depth++;

	_QuickSort(a, left, prev - 1, depth, rule);
	_QuickSort(a, prev + 1, right, depth, rule);
}

// introspective sort 自省快排
void QuickSort(int* a, int left, int right)
{
	// 计算正常递归的深度
	int logn = 0, depth = 0;
	for (int i = 0; i < right; i *= 2)
		logn++;

	_QuickSort(a, left, right, depth, 2 * logn);

}

int main()
{
	int arr[10] = { 6,6,1,4,6,6,9,7,8,6 };
	//QuickSort1(arr, 0, 9);
	
	HeapSort(arr, 10);
	Print(arr, 10);

	return 0;
}